package org.example.algorithm.sliding;

import java.util.HashMap;
import java.util.HashSet;

public class ContainsNearbyDuplicateSolution {

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9,9};
        int k = 3;
        ContainsNearbyDuplicateSolution solution = new ContainsNearbyDuplicateSolution();
        boolean res = solution.containsNearbyDuplicate(nums, k);
        System.out.println(res);
    }

    //使用hash表
    public boolean containsNearbyDuplicate2(int[] nums, int k) {
        if (nums.length < 2) {
            return false;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0;i<nums.length;i++) {
            if (map.containsKey(nums[i]) && i-map.get(nums[i]) <=k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }

    //使用滑动窗口+hashSet
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length < 2) {
            return false;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i=0;i<nums.length;i++) {
            if (i-k>0) {
                set.remove(nums[i-k-1]);
            }
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
        }
        return false;
    }
}